#include "Heap.h"

void initHeap(heap* pheap)
{
	assert(pheap);

	pheap->a = (dataType*)malloc(sizeof(dataType) * INIT_CAPACITY);
	if (pheap->a == NULL) {
		perror("malloc fail");
		return;
	}
	pheap->capacity = INIT_CAPACITY;
	pheap->size = 0;
	printf("The heap has been initialized.\n");
}

void destroyedHeap(heap* pheap)
{
	assert(pheap);
	free(pheap->a);
	pheap->capacity = pheap->size = 0;
	printf("The heap has been destroyed!\n");
}

void swap(dataType* x, dataType* y)
{
	dataType tmp = *x;
	*x = *y;
	*y = tmp;
}
void adjustUp(dataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[child] > a[parent]) 
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
void pushHeap(heap* pheap, dataType x)
{
	assert(pheap);

	if (pheap->size == pheap->capacity) {
		dataType* tmp = (dataType*)realloc(pheap->a,sizeof(dataType) * pheap->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		pheap->a = tmp;
		pheap->capacity *= 2;
	}

	pheap->a[pheap->size] = x;
	adjustUp(pheap->a, pheap->size);

	++pheap->size;
}

int getMax(dataType* a, int x, int y)
{
	if (a[x] > a[y])
	{
		return x;
	}
	else {
		return y;
	}
}
void adjustDown(dataType* a, int parent, int size)
{
	assert(a);

	while (parent < size)
	{
		int lChild = 2 * parent + 1, rChild = 2 * parent + 2, swapChild;
		if (rChild < size) {
			swapChild = getMax(a, lChild, rChild);
		}
		else {
			swapChild = lChild;
		}
		
		if (swapChild < size && a[parent] < a[swapChild]) {
			swap(&a[parent], &a[swapChild]);
			parent = swapChild;
		}
		else {
			break;
		}
	}
}

void popHeap(heap* pheap)
{
	assert(pheap);

	if (pheap->size == 0) {
		printf("The heap has been already emtied!\n");
		return;
	}

	swap(&pheap->a[0], &pheap->a[pheap->size - 1]);
	--pheap->size;
	adjustDown(pheap->a, 0, pheap->size);

}

dataType topHeap(heap* pheap)
{
	assert(pheap);
	assert(!isEmpty(pheap));

	return pheap->a[0];
}

int sizeHeap(heap* pheap)
{
	assert(pheap);

	return pheap->size;
}

bool isEmpty(heap* pheap)
{
	assert(pheap);

	if (pheap->size == 0) {
		return true;
	}
	else {
		return false;
	}
}
